package arithmetic;

import designPatterns.factory.Factory;
import utils.PrintUtil;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

/**
 * @Author: Jie
 * @Date: 2019/2/22 16:07
 * @Function :leetcode 数独 36 37
 * 36. 有效的数独 https://leetcode-cn.com/problems/valid-sudoku/
 *
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 *
 * 求解
 * 方法一 ：简单 递归--》check valid--》结果
 *
 * 方法二：check 每一个空格的可选数字的数量，排序。 先填写最小可选量的格子。
 *
 * 方法三：高级数据结构 dancing link
 *
 */
public class A_17_ValidSudoku {

    private static final int charToNumer = 48;
    private static char[][] clone;

    public static void main(String[] args) {
        char c='1';
//        System.out.println(c);
////        int charToNumer = 0x0030;
//        int charToNumer = 48;
//        c = (char) (c - charToNumer);
        System.out.println("----"+(int)(c - charToNumer));
//
//        System.out.println("7--"+(8/3*3));
//
//        System.out.println((c-0));
//        System.out.println(Character.getNumericValue(c));
//        System.out.println(Character.getNumericValue('a'));
//        System.out.println((int) ('a'));
//
//        HashMap<int[][],Integer> map = new HashMap<>();
//        int[][] block = new int[3][3];
//        block[0][0] = 11;
//        map.put(block,11);
//        block[2][2] = 22;
//        map.put(block,22);
//        System.out.println("map=="+map.get(block));

        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        PrintUtil.printArraysChar(board);

        A_17_ValidSudoku a_17_validSudoku = new A_17_ValidSudoku();
        a_17_validSudoku.solveSudoku(board);
        PrintUtil.printArraysChar(board);

        System.out.println(isValidSudoku(board));
//        PrintUtil.printArraysChar(clone);
    }
    /**
     * leetcode 36
     * 是否有效
     *
     *  * 数字 1-9 在每一行只能出现一次。
     *  * 数字 1-9 在每一列只能出现一次。
     *  * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     *
     * @param board
     * @return
     */
    public static boolean isValidSudoku(char[][] board) {
        //判断每行 列
        for (int i = 0; i < 9; i++) {
            int [] row = new int[10];
            int [] col = new int[10];
            for (int j = 0; j < 9; j++) {
                char r = board[i][j];//j 移动 第二位，row
                if ('.' != r){
                    row[Character.getNumericValue(r)]++;
                }
                char c = board[j][i];//j 移动 第一位， col
                if ('.'!=c){
                    col[Character.getNumericValue(c)]++;
                }
            }
            // 每一行 and 每一列，完成。
            if (isNotValidRow(row) || isNotValidRow(col)){
                return false;
            }
        }

        //判断 block[3][3]
        int[][][] block = new int[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char b = board[i][j];
                if ('.'!=b) {
                    block[i/3][j/3][Character.getNumericValue(board[i][j])]++;
                }
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (isNotValidRow(block[i][j])){
                    return false;
                }
            }
        }

        return true;
    }

    //int[] 0->9 10位。判断是否重复。
    private static boolean isNotValidRow(int[] row) {
        for (int aRow : row) {
            if (aRow > 1) {
                return true;
            }
        }

        return false;
    }




    //leetcode 37.求解 数独
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0)return;
        solve(board);
    }
    /**
     * dfs-->loop--canable number-->next dfs..
     * check 每一个空格的可选数字的数量，排序。（暂时没有排序）
     *
     * 执行用时: 151 ms, 在Sudoku Solver的Java提交中击败了5.62% 的用户
     * 内存消耗:43.9 MB,击败了5.01% 的Java用户
     * @param board
     * @return
     */
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    HashSet<Character> isValid = getValidChars(board, i, j);
                    for (Character anIsValid : isValid) {
                        board[i][j] = anIsValid; //尝试一种可能。
                        if (solve(board)) {
                            return true;
                        } else {
                            //go back 因为。
                            //如果这个选项但是错了 or 完成，那么回溯不影响，for 循环中尝试另一种可能。
                            //只有set . 因为所有操作只是一个数组对象。
                            board[i][j] = '.';
                        }
                    }
                    //9*9 有'.' 不是正确的解，那么返回false
                    return false;
                }
            }
        }
        return true; //默认 有解
    }
    //get possiable input chars
    private HashSet<Character> getValidChars(char[][] board, int indexRow, int indexCol) {
        HashSet<Character> possableChars = new HashSet<>(12, 1.0f);
        for (char k = '1'; k <= '9'; k++) {
            possableChars.add(k);
        }
        //remove row col chars
        for (int k = 0; k < board.length; k++) {
            char r = board[indexRow][k];
            char c = board[k][indexCol];
            possableChars.remove(r);
            possableChars.remove(c);
        }
        //remove block[3][3] chars
        // 计算子网格的起始行和列
        int startRow = indexRow / 3 * 3;
        int startCol = indexCol / 3 * 3;
        for (int k = startRow; k < startRow + 3; k++) { // 遍历行
            for (int m = startCol; m < startCol + 3; m++) { // 遍历列
                char b = board[k][m];
                possableChars.remove(b);
            }
        }
        return possableChars;
    }


    //TODO 练习这个。。。//执行耗时:6 ms,击败了65.04% 的Java用户 ，，内存消耗:40.1 MB,击败了51.90% 的Java用户
    private boolean solve2(char[][] board) {
//          if (row >= board.length || col >= board.length)return false;
        int row = 0, col = 0;
        for (int i = row; i < board.length; i++) {
            for (int j = col; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    //可选
                    for (char k = '1'; k <= '9'; k++) {
                        //有效的继续。
                        if (isValid(board, i, j, k)) {
                            //可选有结果。
                            board[i][j] = k;
                            if (solve2(board)) {//next....
                                return true;
                            } else {//回溯
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true; //默认 有解
    }

    //代测，剪枝。。 //		执行耗时:5 ms,击败了68.86% 的Java用户 //			内存消耗:40.2 MB,击败了19.21% 的Java用户
    private boolean solve3(char[][] board, int row, int col) {
        if (row >= board.length) return true;// 成功遍历完所有格子

        int nextRow = col == board.length - 1 ? row + 1 : row;
        int nextCol = col == board.length - 1 ? 0 : col + 1;

        if (board[row][col] != '.'){
            return solve3(board,nextRow,nextCol);
        }else {
            for (char k = '1'; k <= '9'; k++) {
                //有效的继续。
                if (isValid(board, row, col, k)) {
                    //可选有结果。
                    board[row][col] = k;
                    if (solve3(board, nextRow,nextCol)) {//next....
                        return true;
                    } else {//回溯
                        board[row][col] = '.';//回溯
                    }

                }
            }
        }

        return false; // 无法填充当前格子，回溯
    }

    //solve2 、solve3 共用。
    private boolean isValid(char[][] board, int indexRow, int indexCol, char k) {
        for (int i = 0; i < 9; i++) {
            if (board[indexRow][i] == k || board[i][indexCol] == k) {
                return false;
            }
        }

        //remove block[3][3] chars
        // 计算子网格的起始行和列
        int startRow = indexRow / 3 * 3;
        int startCol = indexCol / 3 * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 遍历行
            for (int m = startCol; m < startCol + 3; m++) { // 遍历列
                if (board[i][m] == k) {
                    return false;
                }
            }
        }
        return true;
    }


}
